package exercises.newcoder.solution;

import java.util.Scanner;

/**
 * <a href="https://www.nowcoder.com/study/live/718/2/11">
 * 第11节 随堂练习-二叉树结构计数</a>
 *
 * @author or2
 * @Description 给出一个整数 n，如果 n < 1，代表空树，否则代表中序遍历的结果为 {1, 2, 3... n}。请输出可能的二叉树结构有多少。
 * @create 2021年09月19日 时间: 11:25
 */
public class NumTrees {

    public static final long MOD = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int nums = scanner.nextInt();

        long[] ans = new long[nums + 1];
        ans[0] = 1;
        ans[1] = 1;
        for (int i = 2; i <= nums; i++) {
            for (int j = 0; j < i; j++) {
                ans[i] += ans[j] * ans[i - 1 - j];
                ans[i] = ans[i] % MOD;
            }
        }

        System.out.println(ans[nums]);
    }
}
